package leetcode.f1t100;

import java.util.ArrayList;
import java.util.List;

/**
 * 在N*N矩阵中放入棋子, 同行,同列, 左斜, 右斜都不可放置两个及以上
 * https://leetcode.com/problems/n-queens/
 * @Author lichongxiao
 * @Date 2022/9/28 11:10
 */
public class Q51_NQueensOutput {


    public List<List<String>> solveNQueens(int n) {
        List<List<String>> answer = new ArrayList<>();
        List<Queens> queensList = new ArrayList<>();
        process(n,0,0,queensList, answer);
        return answer;
    }

    /**
     * n*n的矩阵，到（i，j）位置选择是否放置皇后，queenList是已放置的皇后列表
     * @param n
     * @param i
     * @param j
     * @param queensList
     * @return
     */
    private int process(int n, int i, int j, List<Queens> queensList, List<List<String>> answer) {
        //前进一格后到末尾跳下一行
        if(j==n){
            i++;
            j=0;
        }
        // 有某一行未放置，则直接返回
        if(i>queensList.size()){
            return 0;
        }
        // 放入了所有皇后，返回1
        if(queensList.size()==n){
            List<String> ans = new ArrayList<>();
            for (int k = 0; k < n; k++) {
                ans.add(queensList.get(k).formatOutput());
            }
            answer.add(ans);
            return 1;
        }
        //走完所有格子，返回0
        if(i==n){
            return 0;
        }
        Queens queens = new Queens(i, j, n);
        boolean flag = false;
        for (Queens q : queensList) {
            flag = queens.attackTest(q);
            if(flag){
                break;
            }
        }
        int p1 = process(n,i,j+1,queensList,answer);
        int p2 = 0;
        if(!flag){
            queensList.add(queens);
            p2 = process(n,i,j+1,queensList,answer);
            queensList.remove(queens);
        }
        return p1+p2;
    }



    public class Queens {
        private int x;
        private int y;
        private int n;

        public Queens(int x, int y, int n) {
            this.x = x;
            this.y = y;
            this.n = n;
        }

        public boolean attackTest(Queens queens){
            return this.x == queens.x ||
                    this.y == queens.y ||
                    this.x + this.y == queens.x+queens.y ||
                    this.x -queens.x == this.y - queens.y;
        }

        public String formatOutput(){
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if(i==y){
                    sb.append("Q");
                }else{
                    sb.append(".");
                }
            }
            return sb.toString();
        }
    }
}
